package cn.fansunion.leecode.number;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 448. 找到所有数组中消失的数字<br/>
 * 给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。 <br/>
 * 请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。<br/>
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 * @author wen.lei@brgroup.com
 *
 *         2022-2-19
 */
public class FindAllNumbersDisappearedInAnArray {
    /* 示例 1：
    
    输入：nums = [4,3,2,7,8,2,3,1]
    输出：[5,6]
    示例 2：
    
    输入：nums = [1,1]
    输出：[2]
     
    
    提示：
    
    n == nums.length
    1 <= n <= 105
    1 <= nums[i] <= n
    进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 
    你可以假定返回的数组不算在额外空间内。
    */
    /**
     * 同MissingNumber这个算一类问题；不使用额外空间，但用了“返回数组”这个额外的空间； <br/>
     * 疑问，能做到在原数组nums里修改就搞定吗？<br/>
     * nums[4-1]=1
     * 弊端：ArrayList，LinkedList，数据量很大时，超时了
     * 
     * @param nums
     * @return
     */
    public List<Integer> findDisappearedNumberSet(int[] nums) {
        //List<Integer> existList = new ArrayList<>(nums.length);
        //用Set，16ms；用ArrayList和LinkedList超时了
        Set<Integer> existList = new HashSet<>();
        for (int index = 0; index < nums.length; index++) {
             existList.add(nums[index]);
        }
        // 0表示有值,0不会和nums中的数字冲突
        for (int num : existList) {
            nums[num - 1] = 0;
        }
        List<Integer> notExistList = new ArrayList<>();
        // 非0，表示没有值
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] != 0) {
                notExistList.add(index + 1);
            }
        }
        return notExistList;

    }

    /**
     * 需要额外的空间numsExist，代码更清晰(用时3ms)
     * 
     * @param nums
     * @return
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int[] numsExist = new int[nums.length];
        for (int index = 0; index < nums.length; index++) {
            final int num = nums[index];
            numsExist[num - 1] = 1;
        }
        List<Integer> notExistList = new ArrayList<>();
        for (int index = 0; index < numsExist.length; index++) {
            if (numsExist[index] == 0) {
                notExistList.add(index + 1);
            }
        }
        return notExistList;
    }
}
